package com.example.arithmeticleetcode.leetcode.y2022.m3;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.nio.charset.StandardCharsets;
import java.time.LocalDate;
import java.time.LocalDateTime;
import java.time.Period;
import java.time.format.DateTimeFormatter;
import java.time.temporal.ChronoUnit;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.Stack;
import java.util.UUID;
import java.util.stream.Collectors;

import javax.annotation.meta.When;

import org.apache.commons.lang3.ObjectUtils;
import org.apache.tomcat.util.security.MD5Encoder;

import com.example.arithmeticleetcode.learnArithmetic.quque.DeQuque;
import com.example.arithmeticleetcode.learnArithmetic.quque.Quque;
import com.google.errorprone.annotations.Var;

import lombok.Data;

/**
 * @author: fangzhen@focusmedia.cn
 */
public class Demo {

    /**
     * 2185. 统计包含给定前缀的字符串
     *
     * @param words
     * @param pref
     * @return
     */
    public int prefixCount(String[] words, String pref) {
        int count = 0;
        for (int i = 0; i < words.length; i++) {
            if (words[i].startsWith(pref)) {
                count++;
            }
        }
        return count;
    }

    /**
     * 2104. 子数组范围和
     *
     * @param nums
     * @return
     */
    public long subArrayRanges(int[] nums) {
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                sum += Math.abs(nums[j] - nums[i]);
            }
        }
        return sum;
    }

    /**
     * 2186. 使两字符串互为字母异位词的最少步骤数
     *
     * @param s
     * @param t
     * @return
     */
    public int minSteps(String s, String t) {
        int[] sints = new int[123];
        int[] tints = new int[123];
        for (int i = 0, len = s.length(); i < len; i++) {
            sints[s.charAt(i)]++;
        }
        for (int i = 0, len = t.length(); i < len; i++) {
            tints[t.charAt(i)]++;
        }
        int steps = 0;
        for (int i = 0; i < sints.length; i++) {
            steps += Math.abs(sints[i] - tints[i]);
        }
        return steps;
    }

    /**
     * 504. 七进制数
     *
     * @param n
     * @return
     */
    public String convertToBase7(int n) {
        boolean flag = n < 0;
        if (flag) n = -n;
        StringBuilder sb = new StringBuilder();
        do {
            sb.append(n % 7);
            n /= 7;
        } while (n != 0);
        sb.reverse();
        return flag ? "-" + sb : sb.toString();
    }


    /**
     * 2194. Excel 表中某个范围内的单元格
     *
     * @param s
     * @return
     */
    public List<String> cellsInRange(String s) {
        List<String> result = new ArrayList<>();
        for (int i = s.charAt(0), len = s.charAt(3); i <= len; i++) {
            char tempChar = (char) i;
            for (int j = s.charAt(1), len2 = s.charAt(4); j <= len2; j++) {
                result.add("" + tempChar + (char) j);
            }
        }
        return result;
    }

    /**
     * 2195. 向数组中追加 K 个整数
     *
     * @param nums
     * @param k
     * @return
     */
    public long minimalKSum(int[] nums, int k) {
        int max = -1;
        for (int num : nums) {
            max = Math.max(max, num);
        }
        int[] arr = new int[max];
        for (int num : nums) {
            arr[num]++;
        }
        long sum = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == 0) {
                sum += i;
            }
        }
        return sum;
    }

    /**
     * 599. 两个列表的最小索引总和
     *
     * @param list1
     * @param list2
     * @return
     */
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            map.put(list1[i], i);
        }
        List<String> list = new ArrayList<>();
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < list2.length; i++) {
            if (!map.containsKey(list2[i])) continue;
            int tempMin = i + map.get(list2[i]);
            if (tempMin < min) {
                list.clear();
                ;
                list.add(list2[i]);
                min = tempMin;
            } else if (tempMin == min) {
                list.add(list2[i]);
            }
        }
        return list.toArray(new String[list.size()]);
    }

    /**
     * 720. 词典中最长的单词
     *
     * @param words
     * @return
     */
    public String longestWord(String[] words) {
        String ans = "";
        Set<String> set = new HashSet<>();
        for (String word : words) {
            set.add(word);
        }
        for (String s : set) {
            int n = s.length(), m = ans.length();
            if (n < m || (n == m && s.compareTo(ans) > 0)) continue;
            boolean ok = true;
            for (int i = 1; i < n && ok; i++) {
                String tempS = s.substring(0, i);
                if (!set.contains(tempS)) {
                    ok = false;
                }
            }
            if (ok) {
                ans = s;
            }
        }
        return ans;
    }

    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        getMiddleRootValue(list, root);
        int left = 0, right = list.size() - 1;
        while (left < right) {
            int value = list.get(left) + list.get(right);
            if (value == k) {
                return true;
            }
            if (value < k) {
                left++;
            } else if (value > k) {
                right--;
            }
        }
        return false;
    }

    private void getMiddleRootValue(List<Integer> list, TreeNode root) {
        if (root == null) {
            return;
        }
        getMiddleRootValue(list, root.left);
        list.add(root.val);
        getMiddleRootValue(list, root.right);
    }

    /**
     * 206. 反转链表
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode temp = null;
        while (head != null) {
            ListNode tempNode = head.next;
            head.next = temp;
            temp = head;
            head = tempNode;
        }
        return temp;
    }

    /**
     * 3. 无重复字符的最长子串
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int n = s.length();
        int lIndex = -1, ans = 0;
        for (int i = 0; i < n; i++) {
            if (i != 0) {
                set.remove(s.charAt(i - 1));
            }
            while (lIndex + 1 < n && !set.contains(s.charAt(lIndex + 1))) {
                set.add(s.charAt(lIndex + 1));
                lIndex++;
            }
            ans = Math.max(ans, lIndex - i + 1);
        }
        return ans;
    }

    /**
     * 172. 阶乘后的零
     *
     * @param
     * @return
     */
    public boolean containsDuplicate(int[] nums) {
        // Write your code here
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 37 · 反转一个三位整数
     *
     * @param number
     * @return
     */
    public int reverseInteger(int number) {
        StringBuilder sb = new StringBuilder();
        while (number != 0) {
            int remainder = number / 10;
            number >>= 1;
            if (remainder != 0) {
                sb.append(number);
            }
        }
        System.out.println(sb.reverse().toString());
        final String value = String.valueOf(number);
        final String substring1 = value.substring(0, value.indexOf('0'));
        return Integer.valueOf(new StringBuilder(substring1).reverse().toString());
    }

    /**
     * 面试题 01.08. 零矩阵
     *
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        Set<Integer> colSet = new HashSet<>();
        Set<Integer> rowSet = new HashSet<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    colSet.add(j);
                    rowSet.add(i);
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (rowSet.contains(i) || colSet.contains(j)) {
                    matrix[i][j] = 0;
                }
            }
        }


    }

    /**
     * 面试题 02.01. 移除重复节点
     *
     * @param head
     * @return
     */
    public ListNode removeDuplicateNodes(ListNode head) {
        ListNode ob = head;
        while (ob != null) {
            ListNode oc = ob;
            while (oc.next != null) {
                if (ob.val == oc.next.val) {
                    oc.next = oc.next.next;
                } else {
                    oc = oc.next;
                }
            }
            ob = ob.next;
        }
        return head;
    }

    /**
     * 面试题 02.02. 返回倒数第 k 个节点
     *
     * @param head
     * @param k
     * @return
     */
    public int kthToLast(ListNode head, int k) {
        ListNode fast = head, slow = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

    /**
     * 面试题 02.05. 链表求和
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        int lastNum = 0;
        ListNode result = l1;
        ListNode tempResult = result;
        while (l1 != null || l2 != null) {
            if (l1 != null && l2 != null) {
                int num = lastNum + l1.val + l2.val;
                lastNum = num / 10;
                num = num % 10;
                l1.val = num;
                tempResult = l1;
                l1 = l1.next;
                l2 = l2.next;
            } else if (l1 != null && l2 == null) {
                int num = lastNum + l1.val;
                lastNum = num / 10;
                num = num % 10;
                l1.val = num;
                tempResult = l1;
                l1 = l1.next;
            } else if (l1 == null && l2 != null) {
                int num = lastNum + l2.val;
                lastNum = num / 10;
                num = num % 10;
                l2.val = num;
                tempResult.next = l2;
                tempResult = l2;
                l2 = l2.next;
            }
        }

        if (lastNum > 0) {
            final ListNode listNode = new ListNode(lastNum);
            tempResult.next = listNode;
        }
        return result;
    }

    /**
     * 804. 唯一摩尔斯密码词
     *
     * @param words
     * @return
     */
    public int uniqueMorseRepresentations(String[] words) {
        String[] arr = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
                "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-",
                ".--", "-..-", "-.--", "--.."};
        Set<String> set = new HashSet<>(words.length);
        final StringBuilder sb = new StringBuilder();
        for (String word : words) {
            for (char c : word.toCharArray()) {
                sb.append(arr[c - 97]);
            }
            set.add(sb.toString());
            sb.delete(0, sb.length());
        }
        return set.size();
    }


    /**
     * 面试题 08.09. 括号
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        dfs(n, list, 0, 0, new StringBuilder());
        return list;
    }

    private void dfs(int n, List<String> list, int leftNum, int rightNum, StringBuilder sb) {
        if (leftNum < rightNum || leftNum > n || rightNum > n) {
            return;
        }
        if (leftNum == rightNum && rightNum == n) {
            list.add(sb.toString());
        } else {
            dfs(n, list, leftNum + 1, rightNum, sb.append("("));
            dfs(n, list, leftNum, rightNum + 1, sb.append(")"));
        }
    }

    /**
     * 806. 写字符串需要的行数
     *
     * @param widths
     * @param s
     * @return
     */
    public int[] numberOfLines(int[] widths, String s) {
        int rowNum = 0;
        int remainNum = 0;
        for (int i = 0, len = s.length(); i < len; i++) {
            int tempNum = widths[s.charAt(i) - 'a'];
            if (remainNum + tempNum > 100) {
                remainNum = tempNum;
                rowNum++;
            } else {
                remainNum += tempNum;
            }
        }
        return new int[]{rowNum, remainNum};
    }

    /**
     * 1672. 最富有客户的资产总量
     *
     * @param accounts
     * @return
     */
    public int maximumWealth(int[][] accounts) {
        int maxSum = 0;
        for (int[] account : accounts) {
            int tempSum = 0;
            for (int i : account) {
                tempSum += i;
            }
            maxSum = Math.max(tempSum, maxSum);
        }
        return maxSum;
    }

    /**
     * 819. 最常见的单词
     *
     * @param paragraph
     * @param banned
     * @return
     */
    public String mostCommonWord(String paragraph, String[] banned) {
        final Set<String> bannedSet = Arrays.stream(banned).map(s -> s.toLowerCase()).collect(Collectors.toSet());
        Map<String, Integer> map = new HashMap<>();
        final char[] array = paragraph.toCharArray();
        String ans = null;
        int length = array.length;
        for (int i = 0; i < length; ) {
            if (!Character.isLetter(array[i]) && ++i > 0) continue;
            int j = i;
            while (j < length && Character.isLetter(array[j])) j++;
            String str = paragraph.substring(i, j).toLowerCase();
            i = j + 1;
            if (bannedSet.contains(str)) continue;
            map.put(str, map.getOrDefault(str, 0) + 1);
            if (ans == null || map.get(str) > map.get(ans)) ans = str;
        }
        return ans;
    }

    /**
     * 6070. 计算字符串的数字和
     *
     * @param s
     * @param k
     * @return
     */
    public static String digitSum2(String s, int k) {
        if (s.length() <= k) {
            return s;
        }
        while (s.length() > k) {
            int len = s.length();
            StringBuilder sb = new StringBuilder();
            int count = 0;
            int sum = 0;
            for (int i = 0; i < len; i++) {
                if (count == k) {
                    count = 0;
                    sb.append(sum);
                    sum = 0;
                }
                count++;
                sum += s.charAt(i) - '0';
            }
            if (count != 0) {
                sb.append(sum);
            }
            s = sb.toString();
        }
        return s;
    }

    /**
     * 6070. 计算字符串的数字和
     *
     * @param s
     * @param k
     * @return
     */
    public String digitSum(String s, int k) {
        if (s.length() <= k) {
            return s;
        }
        int len = s.length();
        StringBuilder sb = new StringBuilder();
        int count = 0;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            if (count == k) {
                count = 0;
                sb.append(sum);
                sum = 0;
            }
            count++;
            sum += s.charAt(i) - '0';
        }
        if (count != 0) {
            sb.append(sum);
        }
        s = sb.toString();
        return digitSum(s, k);
    }

    /**
     * 2239. 找到最接近 0 的数字
     *
     * @param nums
     * @return
     */
    public int findClosestNumber(int[] nums) {
        int numberValue = Math.abs(nums[0]);
        int number = nums[0];
        for (int i = 1, len = nums.length; i < len; i++) {
            int tempNum = Math.abs(nums[i]);
            if (numberValue == tempNum) {
                number = Math.abs(number);
                continue;
            }
            if (numberValue > tempNum) {
                numberValue = tempNum;
                number = nums[i];
            }
        }
        return number;
    }

    /**
     * 招商银行-01. 文本编辑程序设计
     *
     * @param article
     * @param index
     * @return
     */
    public String deleteText(String article, int index) {
        if (article.charAt(index) == ' ') return article;
        final String[] strings = article.split(" ");
        if (strings.length == 1) return "";
        StringBuilder sb = new StringBuilder();
        int left = 0, right = 0;
        for (String string : strings) {
            right += string.length();
            if (index >= left && index < right) {
                right++;
                left = right;
                continue;
            }
            sb.append(string).append(" ");
        }
        return sb.toString().trim();
    }

    /**
     * 821. 字符的最短距离
     *
     * @param s
     * @param c
     * @return
     */
    public int[] shortestToChar(String s, char c) {
        int len = s.length();
        int[] arr = new int[len];
        int length = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == c) {
                length = i;
                arr[i] = 0;
                continue;
            }
            arr[i] = Math.abs(length - i);
        }
        for (int i = len - 1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                length = i;
                arr[i] = 0;
                continue;
            }
            arr[i] = Math.min(Math.abs(length - i), arr[i]);
        }
        return arr;
    }

    /**
     * 388. 文件的最长绝对路径
     *
     * @param input
     * @return
     */
    public int lengthLongestPath(String input) {
        int n = input.length();
        int pos = 0;
        int ans = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        while (pos < n) {
            int depth = 1;
            while (pos < n && input.charAt(pos) == '\t') {
                pos++;
                depth++;
            }
            boolean isFile = false;
            int len = 0;
            while (pos < n && input.charAt(pos) != '\n') {
                if (input.charAt(pos) == '.') {
                    isFile = true;
                }
                len++;
                pos++;
            }
            pos++;

            while (stack.size() >= depth) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                len += stack.peek() + 1;
            }
            if (isFile) {
                ans = Math.max(len, ans);
            } else {
                stack.push(len);
            }

        }
        return ans;
    }

    /**
     * 2206. 将数组划分成相等数对
     *
     * @param nums
     * @return
     */
    public boolean divideArray(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() % 2 != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 2206. 将数组划分成相等数对
     *
     * @param nums
     * @return
     */
    public boolean divideArray2(int[] nums) {
        final int[] ints = new int[501];
        for (int num : nums) {
            ints[num]++;
        }
        for (int anInt : ints) {
            if (anInt % 2 != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 824. 山羊拉丁文
     *
     * @param sentence
     * @return
     */
    public String toGoatLatin(String sentence) {
        Set<Character> aeiouSet = Set.of('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U');
        final StringBuilder sb = new StringBuilder();
        final String[] strings = sentence.split(" ");
        for (int i = 0; i < strings.length; i++) {
            if (aeiouSet.contains(strings[i].charAt(0))) {
                sb.append(strings[i]);
                sb.append("ma");
                int tempi = i;
                while (tempi-- >= 0) {
                    sb.append("a");
                }
                sb.append(" ");
                continue;
            }
            sb.append(strings[i].substring(1)).append(strings[i].charAt(0)).append("ma");
            int tempi = i;
            while (tempi-- >= 0) {
                sb.append("a");
            }
            sb.append(" ");
        }
        return sb.substring(0, sb.length() - 1);
    }

    /**
     * 824. 山羊拉丁文
     *
     * @param sentence
     * @return
     */
    public String toGoatLatin2(String sentence) {
        Set<Character> aeiouSet = Set.of('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U');
        final StringBuilder sb = new StringBuilder();
        int firstChar = sentence.charAt(0);
        boolean firstFlag = false;
        int aCount = 1;
        if (aeiouSet.contains(firstChar)) sb.append(firstFlag);
        for (int i = 1, length = sentence.length(); i < length; i++) {
            final char charAt = sentence.charAt(i);
            if (charAt == ' ') {
                if (!aeiouSet.contains(firstChar)) {
                    sb.append(firstChar);
                }
                sb.append("ma");
                int tempACount = aCount;
                while (tempACount-- > 0) {
                    sb.append("a");
                }
                sb.append(" ");
                firstFlag = true;
                continue;
            }
            if (firstFlag) {
                firstFlag = false;
                firstChar = charAt;
                if (!aeiouSet.contains(firstChar)) {
                    continue;
                }
            }
            sb.append(charAt);
        }
        if (!aeiouSet.contains(firstChar)) {
            sb.append(firstChar);
        }
        sb.append("ma");
        while (aCount-- > 0) {
            sb.append("a");
        }
        return sb.toString();
    }

    /**
     * 396. 旋转函数
     *
     * @param nums
     * @return
     */
    public static int maxRotateFunction(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n * 2 + 10];
        for (int i = 1, len = n * 2; i <= len; i++) {
            sum[i] = sum[i - 1] + nums[(i - 1) % n];
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += nums[i - 1] * (i - 1);
        }
        for (int i = n + 1, cur = ans, len = n * 2; i < len; i++) {
            cur += nums[(i - 1) % n] * (n - 1);
            cur -= sum[i - 1] - sum[i - n];
            if (cur > ans) ans = cur;
        }
        return ans;
//        F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
//        F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
//        F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
//        F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26


    }

    /**
     * 2215. 找出两数组的不同
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        Set<Integer> nums1Set = new HashSet<>(nums1.length);
        for (int i : nums1) {
            nums1Set.add(i);
        }
        Set<Integer> nums2Set = new HashSet<>(nums1.length);
        List<Integer> nums2List = new ArrayList<>();
        for (int i : nums2) {
            nums2Set.add(i);
            if (nums1Set.contains(i) || nums2List.contains(i)) {
                continue;
            }
            nums2List.add(i);
        }
        List<Integer> nums1List = new ArrayList<>();
        for (int i : nums1) {
            if (nums2Set.contains(i) || nums1List.contains(i)) {
                continue;
            }
            nums1List.add(i);
        }
        return List.of(nums1List, nums2List);
    }

    /**
     * @param n
     * @return
     */
    public int binaryGap(int n) {
        int last = -1, ans = 1;
        for (int i = 0; n != 0; i++) {
            if ((n & 1) == 1) {
                if (last != -1) {
                    ans = Math.max(ans, i - last);
                }
                last = i;
            }
            i >>= n;
        }
        return ans;

    }

    public static String convert(String s, int numRows) {
        int len = s.length();
        if (len < 2 || numRows < 2) return s;
        char[][] arr = new char[numRows][len];
        int i = 0;
        int rowIdx = 0, colIdx = 0;
        while (i < len) {
            if (rowIdx == 0) {
                while (rowIdx < numRows) {
                    arr[rowIdx++][colIdx] = s.charAt(i);
                }
            } else {
                while (rowIdx != 0) {
                    arr[--rowIdx][colIdx++] = s.charAt(i);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (char[] ints : arr) {
            for (char anInt : ints) {
                if (anInt != 0) {
                    sb.append(anInt);
                }
            }
        }
        return sb.toString();
    }

    /**
     * 6041. 多个数组求交集
     *
     * @param nums
     * @return
     */
    public List<Integer> intersection(int[][] nums) {
        List<Integer> result = new ArrayList<>();
        final int[] ints = new int[1001];
        for (int[] num : nums) {
            for (int i : num) {
                ints[i]++;
            }
        }
        for (int i = 0; i < ints.length; i++) {
            if (ints[i] == 3) {
                result.add(i);
            }
        }
        return result;
    }

    /**
     * 883. 三维形体投影面积
     *
     * @param grid
     * @return
     */
    public int projectionArea(int[][] grid) {
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            int yTempMaxCount = 0;
            int zTempMaxCount = 0;
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] != 0) {
                    ans++;
                }
                yTempMaxCount = Math.max(grid[i][j], yTempMaxCount);
                zTempMaxCount = Math.max(grid[j][i], zTempMaxCount);
            }
            ans += yTempMaxCount;
            ans += zTempMaxCount;
        }
        return ans;
    }

    /**
     * 2249. 统计圆内格点数目
     *
     * @param circles
     * @return
     */
    public int countLatticePoints(int[][] circles) {
        Set<String> set = new HashSet<>();
        for (int[] circle : circles) {
            int l = circle[0] - circle[2], r = circle[0] + circle[2];
            int d = circle[1] - circle[2], u = circle[1] + circle[2];
            for (int i = l + 1; i < r; i++) {
                for (int j = d + 1; j < u; j++) {
                    String temp = "" + i + j;
                    if (set.contains(temp)) continue;
                    set.add(temp);
                }
            }
        }
        return set.size();
    }

    /**
     * 905. 按奇偶排序数组
     *
     * @param nums
     * @return
     */
    public int[] sortArrayByParity(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            if ((nums[left] & 1) == 0) {
                left++;
                if ((nums[right] & 1) != 0) {
                    right--;
                }
                continue;
            }
            while ((nums[right] & 1) == 0 && left < right) {
                right--;
            }
            int temp = nums[left];
            nums[left++] = nums[right];
            nums[right--] = temp;
        }
        return nums;
    }

    /**
     * 908. 最小差值 I
     *
     * @param nums
     * @param k
     * @return
     */
    public int smallestRangeI(int[] nums, int k) {
        int minValue = Integer.MAX_VALUE;
        int maxValue = Integer.MIN_VALUE;
        for (int num : nums) {
            minValue = Math.min(minValue, num);
            maxValue = Math.max(maxValue, num);
        }
        return maxValue - minValue <= 2 * k ? 0 : maxValue - minValue - 2 * k;
    }

    /**
     * 1305. 两棵二叉搜索树中的所有元素
     *
     * @param root1
     * @param root2
     * @return
     */
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        getAllElementsDFS(root1, list1);
        getAllElementsDFS(root2, list2);
        int m = list1.size(), n = list2.size(), i = 0, j = 0;
        while (i < m || j < n) {
            int a = i < m ? list1.get(i) : Integer.MAX_VALUE, b = j < n ? list2.get(j) : Integer.MAX_VALUE;
            if (a <= b) {
                i++;
                list.add(a);
            } else {
                j++;
                list.add(b);
            }
        }
        return list;
    }

    private void getAllElementsDFS(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        getAllElementsDFS(root.left, list);
        list.add(root.val);
        getAllElementsDFS(root.right, list);
    }

    /**
     * 1823. 找出游戏的获胜者
     *
     * @param n
     * @param k
     * @return
     */
    public static int findTheWinner(int n, int k) {
        boolean[] arr = new boolean[n];
        int start = 0;
        int cycle = n;
        while (cycle > 1) {
            int count = 0;
            while (count < k) {
                if (start == n) {
                    start = 0;
                }
                if (start < n && !arr[start]) {
                    count++;
                }
                start++;
            }
            arr[start - 1] = true;
            cycle--;
        }
        for (int i = 0; i < n; i++) {
            if (!arr[i]) {
                return i + 1;
            }
        }
        return -1;
    }

    /**
     * 713. 乘积小于 K 的子数组
     *
     * @param nums
     * @param k
     * @return
     */
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int start = 0, n = nums.length;
        int count = 0;
        while (start < n) {
            int sum = 1;
            int tempStart = start;
            while (tempStart < n) {
                sum *= nums[tempStart];
                if (sum < k) {
                    count++;
                    tempStart++;
                    continue;
                }
                break;
            }
            start++;
        }
        return count;
    }

    /**
     * 433. 最小基因变化
     *
     * @param start
     * @param end
     * @param bank
     * @return
     */
    public int minMutation(String start, String end, String[] bank) {
        if (start.equals(end)) return 0;
        Set<String> cnt = new HashSet<>();
        for (String s : bank) {
            cnt.add(s);
        }
        if (!cnt.contains(end)) return -1;
        Set<String> visited = new HashSet<>();
        char[] keys = {'A', 'C', 'G', 'T'};
        Queue<String> queue = new ArrayDeque<>();
        queue.offer(start);
        visited.add(start);
        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String current = queue.poll();
                for (int j = 0; j < 8; j++) {
                    for (int k = 0; k < 4; k++) {
                        if (keys[k] != current.charAt(j)) {
                            StringBuilder sb = new StringBuilder(current);
                            sb.setCharAt(j, keys[k]);
                            String next = sb.toString();
                            if (!visited.contains(next) && cnt.contains(next)) {
                                if (next.equals(end)) {
                                    return step;
                                }
                                visited.add(next);
                                queue.offer(next);
                            }
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }

    /**
     * 442. 数组中重复的数据
     *
     * @param nums
     * @return
     */
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int[] numCountArr = new int[nums.length + 1];
        for (int num : nums) {
            numCountArr[num]++;
        }
        for (int i = 0, len = numCountArr.length; i < len; i++) {
            if (numCountArr[i] == 2) {
                list.add(i);
            }
        }
        return list;

    }

    /**
     * 942. 增减字符串匹配
     *
     * @param s
     * @return
     */
    public int[] diStringMatch(String s) {
        int len = s.length();
        final int[] ints = new int[s.length() + 1];
        int dValue = len, iValue = 0;
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == 'D') {
                ints[i] = dValue--;
            } else {
                ints[i] = iValue++;
            }
        }
        ints[len] = iValue++;
        return ints;
    }

    /**
     * 2264. 字符串中最大的 3 位相同数字
     *
     * @param num
     * @return
     */
    public String largestGoodInteger(String num) {
        int len = num.length();
        int fastIndex = 1;
        int slowIndex = 0;
        String result = null;
        while (fastIndex < len) {
            if (num.charAt(fastIndex) == num.charAt(slowIndex)) {
                fastIndex++;
            } else {
                slowIndex = fastIndex;
                fastIndex++;
            }
            if (fastIndex - slowIndex > 2) {
                if (result == null) {
                    result = num.substring(slowIndex, fastIndex);
                    continue;
                }
                if (result.charAt(0) < num.charAt(slowIndex)) {
                    result = num.substring(slowIndex, fastIndex);
                }
            }
        }

        return result == null ? "" : result;
    }

    /**
     * 2264. 字符串中最大的 3 位相同数字
     *
     * @param num
     * @return
     */
    public String largestGoodInteger2(String num) {
        int len = num.length();
        char[] charArray = num.toCharArray();
        int fastIndex = 1;
        int slowIndex = 0;
        String result = null;
        while (fastIndex < len) {
            if (charArray[fastIndex] == charArray[slowIndex]) {
                fastIndex++;
            } else {
                slowIndex = fastIndex;
                fastIndex++;
            }
            if (fastIndex - slowIndex < 3) {
                continue;
            }
            if (result == null) {
                result = new String(charArray, slowIndex, 3);
                continue;
            }
            if (result.charAt(0) < num.charAt(slowIndex)) {
                result = new String(charArray, slowIndex, 3);
            }
        }

        return result == null ? "" : result;
    }

    /**
     * 2224. 转化时间需要的最少操作数
     *
     * @param current
     * @param correct
     * @return
     */
    public int convertTime(String current, String correct) {
        String[] correctArr = correct.split(":");
        String[] currentArr = current.split(":");
        int currentHour = Integer.valueOf(currentArr[0]);
        int currentMin = Integer.valueOf(currentArr[1]);
        int correctHour = Integer.valueOf(correctArr[0]);
        int correctMin = Integer.valueOf(correctArr[1]);
        int diffMin = correctHour * 60 + correctMin - currentHour * 60 - currentMin;
        int count = diffMin / 60;
        diffMin = diffMin % 60;
        count += diffMin / 15;
        diffMin = diffMin % 15;
        count += diffMin / 5;
        diffMin = diffMin % 5;
        count += diffMin / 1;
        diffMin = diffMin % 1;
        return count;
    }

    /**
     * 944. 删列造序
     *
     * @param strs
     * @return
     */
    public int minDeletionSize(String[] strs) {
        int colLen = strs[0].length();
        int rowLen = strs.length;
        int result = 0;
        for (int i = 0; i < colLen; i++) {
            char preChar = strs[0].charAt(i);
            for (int j = 1; j < rowLen; j++) {
                char curChar = strs[j].charAt(i);
                if (preChar > curChar) {
                    result++;
                    break;
                }
                preChar = curChar;
            }
        }
        return result;
    }

    /**
     * 面试题 01.05. 一次编辑
     *
     * @param first
     * @param second
     * @return
     */
    public boolean oneEditAway(String first, String second) {
        int firstLen = first.length(), secondLen = second.length();
        if (firstLen - secondLen > 1) {
            return false;
        }
        //相等就是替换
        if (firstLen == secondLen) {
            int count = 0;
            for (int i = 0; i < firstLen; i++) {
                if (first.charAt(i) != second.charAt(i)) {
                    count++;
                }
                if (count > 1) {
                    return false;
                }
            }
            return true;
        }
        //不等就是需要删除或者新增
        firstLen--;
        secondLen--;
        int count = 0;
        while (firstLen >= 0 || secondLen >= 0) {
            if (firstLen >= 0 && secondLen >= 0) {
                if (first.charAt(firstLen) == second.charAt(secondLen)) {
                    firstLen--;
                    secondLen--;
                } else {
                    count++;
                    if (firstLen > secondLen) {
                        firstLen--;
                    } else {
                        secondLen--;
                    }
                }
            } else {
                if (count == 0) return true;
                else return false;
            }
            if (count > 1) return false;
        }
        return true;
    }

    /**
     * 2180. 统计各位数字之和为偶数的整数个数
     *
     * @param num
     * @return
     */
    public int countEven(int num) {
        int start = 1;
        int count = 0;
        while (start <= num) {
            int tempStart = start;
            int sum = 0;
            while (tempStart > 0) {
                sum += tempStart % 10;
                tempStart /= 10;
            }
            if ((sum & 1) != 1) {
                count++;
            }
            start++;
        }
        return count;
    }

    /**
     * 5299. 找到一个数字的 K 美丽值
     *
     * @param num
     * @param k
     * @return
     */
    public int divisorSubstrings(int num, int k) {
        String numStr = String.valueOf(num);
        int result = 0;
        for (int i = 0, len = numStr.length() - k; i <= len; i++, k++) {
            if (num % Integer.valueOf(numStr.substring(i, k)) == 0) {
                result++;
            }
        }
        return result;
    }

    /**
     * 面试题 04.06. 后继者
     *
     * @param root
     * @param p
     * @return
     */
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode pre = null, current = root;
        while (!stack.isEmpty() || current != null) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            if (pre == p) {
                return current;
            }
            pre = current;
            current = current.right;
        }
        return current;
    }

    /**
     * 94. 二叉树的中序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root.left);
                root = root.left;
            }
            TreeNode node = stack.pop();
            result.add(node.val);
            root = root.right;
        }
        return result;
    }

    /**
     * 98. 验证二叉搜索树
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        TreeNode pre = null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (pre != null && pre.val >= root.val) {
                return false;
            }
            pre = root;
            root = root.right;
        }
        return true;
    }

    public boolean isAlienSorted(String[] words, String order) {
        for (String word : words) {
            int minIndex = order.indexOf(word.charAt(0));
            for (int i = 0; i < word.length(); i++) {
                int curIndex = order.indexOf(word.charAt(i));
                if (curIndex < minIndex) {
                    minIndex = curIndex;
                    System.out.println(curIndex);
                }
            }
            if (minIndex != word.length() - 1) {
                return false;
            }
        }
        return true;
    }


    /**
     * 449. 序列化和反序列化二叉搜索树
     */
    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            serializeAfter(list, root);
            String result = list.toString();
            return result.substring(1, result.length() - 1);
        }

        private void serializeAfter(List<Integer> list, TreeNode root) {
            if (root == null) {
                return;
            }
            serializeAfter(list, root.left);
            serializeAfter(list, root.right);
            list.add(root.val);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.isEmpty()) {
                return null;
            }
            String[] arr = data.split(", ");
            Deque<Integer> deque = new ArrayDeque<>();
            for (int i = 0, len = arr.length; i < len; i++) {
                deque.push(Integer.valueOf(arr[i]));
            }
            return deserialize2(Integer.MIN_VALUE, Integer.MAX_VALUE, deque);
        }

        private TreeNode deserialize2(int lower, int upper, Deque<Integer> stack) {
            if (stack.isEmpty() || lower > stack.peek() || stack.peek() > upper) {
                return null;
            }
            Integer val = stack.pop();
            TreeNode node = new TreeNode(val);
            node.right = deserialize2(val, upper, stack);
            node.left = deserialize2(lower, val, stack);
            return node;
        }
    }

    /**
     * 2200. 找出数组中的所有 K 近邻下标
     *
     * @param nums
     * @param key
     * @param k
     * @return
     */
    public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
        List<Integer> result = new ArrayList<>();
        List<Integer> indexList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == key) {
                indexList.add(i);
            }
        }
        if (indexList.size() == 0) return result;
        for (int i = 0; i < nums.length; i++) {
            for (int keyIndex : indexList) {
                if (Math.abs(i - keyIndex) <= k) {
                    result.add(i);
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 2200. 找出数组中的所有 K 近邻下标
     *
     * @param nums
     * @param key
     * @param k
     * @return
     */
    public List<Integer> findKDistantIndices2(int[] nums, int key, int k) {
        List<Integer> result = new ArrayList<>();
        int slow = 0;
        for (int i = 0, len = nums.length; i < len; i++) {
            if (nums[i] == k) {
                slow = Math.max(slow, i - k);
                int end = Math.min(i + k, len - 1);
                while (slow <= end) {
                    result.add(slow++);
                }
            }
        }
        return result;
    }

    /**
     * 961. 在长度 2N 的数组中找出重复 N 次的元素
     *
     * @param nums
     * @return
     */
    public int repeatedNTimes(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.contains(num)) {
                set.add(num);
            }
            return num;
        }
        return -1;

    }

    /**
     * 464. 我能赢吗
     *
     * @param maxChoosableInteger
     * @param desiredTotal
     * @return
     */
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        int firstTotal = 0, sencondTotal = 0;
        boolean flag = true;
        int firstChoose = 1;
        while (firstChoose < maxChoosableInteger) {
            if (firstTotal > desiredTotal) {
                return true;
            }
            if (sencondTotal > maxChoosableInteger) {
                return false;
            }
            if (flag) {
                firstTotal += firstChoose;
                firstChoose++;
                flag = false;
            } else {
                sencondTotal += maxChoosableInteger;
                maxChoosableInteger--;
                flag = true;
            }
        }
        return true;
    }

    /**
     * 2144. 打折购买糖果的最小开销
     *
     * @param cost
     * @return
     */
    public int minimumCost(int[] cost) {
        Arrays.sort(cost);
        int sum = 0;
        int count = 0;
        for (int i = cost.length - 1; i >= 0; i--) {
            if (count == 2) {
                count = 0;
                continue;
            }
            sum += cost[i];
            count++;
        }
        return sum;
    }

    /**
     * 6074. 字母在字符串中的百分比
     *
     * @param s
     * @param letter
     * @return
     */
    public int percentageLetter(String s, char letter) {
        int len = s.length();
        int count = 0;
        for (int i = len - 1; i >= 0; i--) {
            if (s.charAt(i) == letter) count++;
        }
        return count * 100 / len;
    }

    /**
     * 965. 单值二叉树
     *
     * @param root
     * @return
     */
    public boolean isUnivalTree(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        int value = root.val;
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.pop();
            while (node != null) {
                deque.push(node);
                node = node.left;
            }
            TreeNode treeNode = deque.pop();
            if (value != treeNode.val) {
                return false;
            }

        }
        return true;
    }

    /**
     * 699. 掉落的方块
     *
     * @param positions
     * @return
     */
    public List<Integer> fallingSquares(int[][] positions) {
        List<Integer> list = new ArrayList<>();
        list.add(positions[0][1]);
        int prePoint = positions[0][0] + positions[0][1];
        int preHigh = positions[0][1];
        for (int i = 1; i < positions.length; i++) {
            if (prePoint <= positions[i][0]) {
                prePoint = positions[i][0] + positions[i][1];
                preHigh = Math.max(positions[i][1], preHigh);
                list.add(preHigh);
                continue;
            }
            prePoint = positions[i][0] + positions[i][1];
            preHigh += positions[i][1];
            preHigh = Math.max(positions[i][1], preHigh);
            list.add(preHigh);
        }
        return list;
    }

    /**
     * 面试题 17.11. 单词距离
     *
     * @param words
     * @param word1
     * @param word2
     * @return
     */
    public int findClosest(String[] words, String word1, String word2) {
        int index1 = -1, index2 = -1;
        int ans = words.length;
        for (int i = 0, len = ans; i < ans; i++) {
            if (words[i].equals(word1)) {
                index1 = i;
            }
            if (words[i].equals(word2)) {
                index2 = i;
            }
            if (index1 >= 0 && index2 >= 0) {
                ans = Math.min(ans, Math.abs(index1 - index2));
            }
        }
        return ans;
    }

    /**
     * 剑指 Offer II 012. 左右两边子数组的和相等
     *
     * @param nums
     * @return
     */
    public int pivotIndex(int[] nums) {
        for (int i = 1, j = 0, len = nums.length; i < len; i++, j++) {
            nums[i] += nums[j];
        }
        System.out.println(Arrays.toString(nums));
        int len = nums.length - 1;
        if (nums[len] - nums[0] == 0) return 0;
        for (int i = 1, j = 0; i < len; i++) {
            System.out.print(nums[j]);
            System.out.println(nums[j] + " == " + nums[len] + " - " + nums[i]);
            if (nums[j] == nums[len] - nums[i]) {
                return i;
            }
        }
        if (nums[len - 1] == 0) return len;
        return -1;
    }

    /**
     * 468. 验证IP地址
     *
     * @param queryIP
     * @return
     */
    public static String validIPAddress(String queryIP) {
        if (queryIP.contains(".")) {
            if (queryIP.charAt(0) == '.' || queryIP.charAt(queryIP.length() - 1) == '.') return "Neither";
            final String[] split = queryIP.split("\\.");
            if (split.length != 4) return "Neither";
            for (String s : split) {
                //首字母为零
                int len = s.length();
                if (s.charAt(0) == '0' && len != 1) return "Neither";
                if (len == 0) return "Neither";
                for (int i = 1; i < len; i++) {
                    char c = s.charAt(i);
                    if (c < '0' || c > '9') {
                        return "Neither";
                    }
                }
                int numStr = Integer.valueOf(s);
                if (numStr > 255) return "Neither";
            }
            return "IPv4";
        }
        if (queryIP.contains(":")) {
            if (queryIP.charAt(0) == ':' || queryIP.charAt(queryIP.length() - 1) == ':') return "Neither";
            final String[] split = queryIP.split("\\:");
            if (split.length != 8) return "Neither";
            for (String s : split) {
                //首字母为零
                int len = s.length();
                if (len == 0) return "Neither";
                for (int i = 1; i < len; i++) {
                    char c = s.charAt(i);
                    if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'F') || (c >= 'a' && c <= 'f')) {
                        continue;
                    }
                    return "Neither";
                }
                if (len > 4) return "Neither";
            }
            return "IPv6";
        }
        return "Neither";
    }

    /**
     * 剑指 Offer II 024. 反转链表
     *
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        ListNode result = null;
        while (head != null) {
            ListNode tempNode = head.next;
            head.next = result;
            result = head;
            head = tempNode;
        }
        return result;
    }

    /**
     * 剑指 Offer II 006. 排序数组中两个数字之和
     *
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum(int[] numbers, int target) {
        int leftIndex = 0, rightIndex = numbers.length - 1;
        while (leftIndex < rightIndex) {
            int leftAndRightSum = numbers[leftIndex] + numbers[rightIndex];
            if (leftAndRightSum > target) {
                rightIndex--;
            } else if (leftAndRightSum < target) {
                leftIndex++;
            } else {
                return new int[]{leftIndex, rightIndex};
            }
        }
        return new int[]{leftIndex, rightIndex};
    }

    /**
     * 6090. 极大极小游戏
     *
     * @param nums
     * @return
     */
    public static int minMaxGame(int[] nums) {
        int len = nums.length;
        int index = 0;
        while (len != 1) {
            for (int i = 0; i < len; i++) {
                if ((index & 1) == 1) {
                    nums[index++] = Math.max(nums[i], nums[++i]);
                } else {
                    nums[index++] = Math.min(nums[i], nums[++i]);
                }
            }
            len >>= 1;
            index = 0;
        }
        return nums[index];
    }

    /**
     * 6092. 替换数组中的元素
     *
     * @param nums
     * @param operations
     * @return
     */
    public int[] arrayChange(int[] nums, int[][] operations) {
        Map<Integer, Integer> mapKey = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            mapKey.put(nums[i], i);
        }
        for (int[] operation : operations) {
            int value = mapKey.get(operation[0]);
            mapKey.put(operation[1], value);
            mapKey.remove(operation[0]);
        }
        for (Map.Entry<Integer, Integer> entry : mapKey.entrySet()) {
            nums[entry.getValue()] = entry.getKey();
        }
        return nums;
    }

    /**
     * 6091. 划分数组使最大差为 K
     *
     * @param nums
     * @param k
     * @return
     */
    public int partitionArray(int[] nums, int k) {
        if (k == 0) return nums.length;
        Arrays.sort(nums);
        int preValue = nums[0];
        int count = 1;
        for (int i = 1, len = nums.length; i < len; i++) {
            if (preValue + k >= nums[i]) {
                continue;
            }
            preValue = nums[i];
            count++;
        }
        return count;
    }

    /**
     * 732. 我的日程安排表 III
     */
    class MyCalendarThree {

        private List<int[]> list;

        public MyCalendarThree() {
            this.list = new ArrayList<>();
        }

        public int book(int start, int end) {
            int count = 1;
            for (int[] ints : list) {
                if (end < ints[0] || start > ints[1]) {
                    continue;
                }
                count++;
            }
            list.add(new int[]{start, end});
            return count;
        }
    }

    /**
     * 1037. 有效的回旋镖
     *
     * @param points
     * @return
     */
    public boolean isBoomerang(int[][] points) {
        System.out.println((points[0][0] - points[1][0]) * (points[0][1] - points[2][1]));
        System.out.println((points[0][0] - points[2][0]) * (points[0][1] - points[1][1]));
        return (points[0][0] - points[1][0]) * (points[0][1] - points[2][1]) == (points[0][0] - points[2][0]) * (points[0][1] - points[1][1]);
    }

    /**
     * 926. 将字符串翻转到单调递增
     *
     * @param s
     * @return
     */
    public int minFlipsMonoIncr(String s) {
        int zeroCount = 0, oneCount = 0;
        boolean flag = false;
        for (int i = 0; i < s.length(); i++) {
            char tempChar = s.charAt(i);
            if (!flag && tempChar == '1') {
                flag = true;
                oneCount++;
                continue;
            }
            if (tempChar == '1') {
                oneCount++;
            } else {
                zeroCount++;
            }
        }
        return Math.min(zeroCount, oneCount);
    }

    /**
     * 6095. 强密码检验器 II
     *
     * @param password
     * @return
     */
    public boolean strongPasswordCheckerII(String password) {
        if (password.length() < 8) return false;
        String specialChar = "!@#$%^&*()-+";
        char preChar = password.charAt(0);
        boolean smallCharFlag = Character.isLowerCase(preChar),
                bigCharFlag = Character.isUpperCase(preChar),
                numFlag = Character.isDigit(preChar), specialCharFlag = specialChar.indexOf(preChar) != -1;

        for (int i = 1, len = password.length(); i < len; i++) {
            char tempChar = password.charAt(i);
            if (preChar == tempChar) {
                return false;
            }
            if (Character.isLowerCase(tempChar)) {
                smallCharFlag = true;
            } else if (Character.isUpperCase(tempChar)) {
                bigCharFlag = true;
            } else if (Character.isDigit(tempChar)) {
                numFlag = true;
            } else if (specialChar.indexOf(tempChar) != -1) {
                specialCharFlag = true;
            }
            preChar = tempChar;
        }
        return smallCharFlag && bigCharFlag && numFlag && specialCharFlag;
    }

    /**
     * 6096. 咒语和药水的成功对数
     *
     * @param spells
     * @param potions
     * @param success
     * @return
     */
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        Arrays.sort(spells);
        for (int i = 0, len = spells.length; i < len; i++) {
            int count = 0;
            long spellValue = spells[i];
            for (int j = 0, len2 = potions.length; j < len2; j++) {
                long potionValue = potions[j];
                if (spellValue * potionValue < success) {
                    continue;
                }
                count += len2 - j;
                break;
            }
            spells[i] = count;
        }

        return spells;
    }

    /**
     * 5259. 计算应缴税款总额
     *
     * @param brackets
     * @param income
     * @return
     */
    public static double calculateTax(int[][] brackets, int income) {
        double taxMoney = 0;
        if (income <= 0) return taxMoney;
        if (income >= brackets[0][0]) {
            taxMoney += (double) brackets[0][0] * brackets[0][1] / 100;
        } else {
            taxMoney += (double) income * brackets[0][1] / 100;
        }
        income -= brackets[0][0];
        for (int i = 1, len = brackets.length; i < len; i++) {
            if (income <= 0) break;
            int cur = brackets[i][0] - brackets[i - 1][0];
            if (income >= cur) {
                taxMoney += (double) cur * brackets[i][1] / 100;
            } else {
                taxMoney += (double) income * brackets[i][1] / 100;
            }
            income -= cur;
        }
        return taxMoney;
    }

    /**
     * 1051. 高度检查器
     *
     * @param heights
     * @return
     */
    public int heightChecker(int[] heights) {
        int[] arr = new int[heights.length];
        System.arraycopy(heights, 0, arr, 0, heights.length);
        Arrays.sort(heights);
        int count = 0;
        for (int i = 0, len = arr.length; i < len; i++) {
            if (arr[i] != heights[i]) {
                count++;
            }
        }
        return count;

    }

    /**
     * 498. 对角线遍历
     *
     * @param mat
     * @return
     */
    public int[] findDiagonalOrder(int[][] mat) {
        int rowLength = mat.length;
        int colLength = mat[0].length;
        int[] arr = new int[rowLength * colLength];
        int rowIndex = 0;
        int colIndex = 0;
        int index = 0;
        boolean rowFlag = false;
        boolean colFlag = false;
        while (index < arr.length) {
            arr[index++] = mat[rowIndex][colIndex];

        }
        return arr;
    }

    /**
     * 719. 找出第 K 小的数对距离
     *
     * @param nums
     * @param k
     * @return
     */
    public int smallestDistancePair(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0, len = nums.length; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                list.add(Math.min(Math.abs(nums[i] - nums[j]) - 1, 0));
            }
        }
        Collections.sort(list);
        return list.get(k - 1);
    }

    public int findPairs(int[] nums, int k) {
        int count = 0;

        for (int i = 0, len = nums.length; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (Math.abs(nums[i] - nums[j]) == k) count++;
            }
        }
        return count;
    }

    /**
     * 1089. 复写零
     *
     * @param arr
     */
    public void duplicateZeros(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int count = 0;
        for (int i = 0, len = arr.length; i < len; i++) {
            stack.push(arr[i]);
            count++;
            if (arr[i] == 0 && count < len) {
                count++;
                stack.push(0);
            }
            if (count == len) {
                break;
            }
        }
        int i = arr.length - 1;
        while (!stack.isEmpty()) {
            arr[i--] = stack.pop();
        }
    }

    /**
     * 顺丰03. 收件节节高
     *
     * @param nums
     * @return
     */
    public int findMaxCI(int[] nums) {
        int count = 1;
        int result = 1;
        int pre = nums[0];
        for (int i = 1, len = nums.length; i < len; i++) {
            if (pre < nums[i]) {
                count++;
                pre = nums[i];
                continue;
            }
            pre = nums[i];
            result = Math.max(result, count);
            count = 1;
        }
        return Math.max(result, count);
    }

    /**
     * 1108. IP 地址无效化
     *
     * @param address
     * @return
     */
    public String defangIPaddr(String address) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0, len = address.length(); i < len; i++) {
            if (address.charAt(i) == '.') {
                sb.append("[.]");
                continue;
            }
            sb.append(address.charAt(i));
        }
        return sb.toString();
    }

    /**
     * 513. 找树左下角的值
     *
     * @param root
     * @return
     */

    public int findBottomLeftValue(TreeNode root) {
        int ret = 0;
        Queue<TreeNode> quque = new ArrayDeque<>();
        quque.offer(root);
        while (!quque.isEmpty()) {
            final TreeNode node = quque.poll();
            if (node.right != null) {
                quque.offer(node.right);
            }
            if (node.left != null) {
                quque.offer(node.left);
            }
            ret = node.val;
        }
        return ret;
    }

    /**
     * 515. 在每个树行中找最大值
     *
     * @param root
     * @return
     */
    public List<Integer> largestValues(TreeNode root) {
        if (root == null) return null;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.push(root);
        List<Integer> list = new ArrayList<>();
        while (!deque.isEmpty()) {
            int size = deque.size();
            int max = Integer.MIN_VALUE;
            while (size-- > 0) {
                final TreeNode node = deque.poll();
                max = Math.max(max, node.val);
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
            list.add(max);
        }
        return list;
    }

    /**
     * 6104. 统计星号
     *
     * @param s
     * @return
     */
    public int countAsterisks(String s) {
        String[] arrs = s.split("|");
        int count = 0;
        System.out.println(Arrays.toString(arrs));
        for (int i = 0, len = arrs.length; i < len; i +=2) {
            for (int j = 0, sLen = arrs[i].length(); j < sLen; j++) {
                if (arrs[i].charAt(j) == '*') {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 6101. 判断矩阵是否是一个 X 矩阵
     *
     * @param grid
     * @return
     */
    public boolean checkXMatrix(int[][] grid) {
        for (int i = 0, m = grid.length; i < m; i++) {
            for (int j = 0, n = grid[i].length; j < n; j++) {
                if (i == j || i + j + 1 == m) {
                    if (grid[i][j] == 0) {
                        return false;
                    }
                } else if (grid[i][j] != 0) {
                    return false;
                }
            }
        }
        return true;
    }


//    public static void main(String[] args) {
//        int[][] arr = {{3, 50}, {7, 10}, {12, 25}};
//        calculateTax(arr, 10);
//        String key = "qualify-upload-module/e31bf240464d41e4b904fcefb2c48af2/edeed65bbe1d405f8cdc1396cfb1adda";
//        System.out.println(key.substring(key.lastIndexOf('/') + 1));
//    }

    /**
     * insert sort
     *
     * @param arr time O(N^2) space O(1) stable
     */
    public static void insertSort(int[] arr) {

        for (int i = 1, len = arr.length; i < len; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
            System.out.println(Arrays.toString(arr));
        }
    }

    /**
     * select sort
     *
     * @param arr time O(N^2) space O(1) stable
     */
    public static void selectSort(int[] arr) {
        for (int i = 0, len = arr.length; i < len; i++) {
            int minIndex = i;
            for (int j = i + 1; j < len; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
            System.out.println(Arrays.toString(arr));
        }
    }

    /**
     * bubble sort
     *
     * @param arr time O(N^2) space O(1) stable
     */
    public static void bubbleSort(int[] arr) {
        for (int i = arr.length; i > 1; i--) {
            boolean noSwap = true;
            for (int j = 1; j < i; j++) {
                if (arr[j - 1] > arr[j]) {
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                    noSwap = false;
                }
            }
            System.out.println(Arrays.toString(arr));
            if (noSwap) {
                System.out.println(i);
                break;
            }
        }
    }

    /**
     * shell sort
     *
     * @param arr time O(N^2) space O(1) stable
     */
    public static void shellSort(int[] arr) {
        int len = arr.length;
        int j;
        //inc
        for (int inc = len / 2; inc > 0; inc /= 2) {
            //insert sort
            for (int i = inc; i < len; i++) {
                int key = arr[i];
                for (j = i; j >= inc && key < arr[j - inc]; j -= inc) {
                    arr[j] = arr[j - inc];
                }
                arr[j] = key;
            }
            System.out.println(Arrays.toString(arr));
        }
    }

    /**
     * 6108. 解密消息
     *
     * @param key
     * @param message
     * @return
     */
    public String decodeMessage(String key, String message) {
        Map<Character, Character> map = new HashMap<>();
        char a = 'a';
        for (int i = 0, len = key.length(); i < len; i++) {
            final char c = key.charAt(i);
            if (c == ' ' || map.containsKey(c)) {
                continue;
            }
            map.put(c, a++);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0, len = message.length(); i < len; i++) {
            final char c = message.charAt(i);
            if (c == ' ') {
                sb.append(c);
                continue;
            }
            sb.append(map.get(c));
        }
        return sb.toString();
    }

    /**
     * 6111. 螺旋矩阵 IV
     *
     * @param m
     * @param n
     * @param head
     * @return
     */
    public int[][] spiralMatrix(int m, int n, ListNode head) {
        int[][] arr = new int[m][n];
        int rowUp = 0;
        int rowDown = m - 1;
        int colLeft = 0;
        int colRight = n - 1;
        int row = 0, col = 0;
        int i = 0, len = m * n;
        while (i < len) {
            if (row < rowDown)
            while (head != null) {

            }
        }
        return arr;
    }

    
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        List<List<Integer>> result = new ArrayList<>();
        int diff = Integer.MAX_VALUE;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] <= diff) {
                diff = arr[i] - arr[i - 1];
            }
        }
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] == diff) {
                result.add(List.of(arr[i], arr[i - 1]));
            }
        }
        return result;
    }

    /**
     * 648. 单词替换
     *
     * @param dictionary
     * @param sentence
     * @return
     */
    public String replaceWords(List<String> dictionary, String sentence) {
        final String[] arr = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String s : arr) {
            String tempStr = "";
            for (String dic : dictionary) {
                if (s.startsWith(dic) && tempStr.length() < dic.length()) {
                    tempStr = dic;
                }
            }
            sb.append("".equals(tempStr) ? s : tempStr).append(" ");
        }
        return sb.toString().trim();
    }

    /**
     * 1252. 奇数值单元格的数目
     * 
     * @param m
     * @param n
     * @param indices
     * @return
     */
    public int oddCells(int m, int n, int[][] indices) {
        int[][] arr = new int[m][n];
        for (int[] index : indices) {
            for (int i = 0; i < n; i++) {
                arr[index[0]][i]++;
            }
            for (int i = 0; i < m; i++) {
                arr[i][index[1]]++;
            }
        }
        int count = 0;
        for (int[] ints : arr) {
            for (int i : ints) {
                if ((i & 1) == 1) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 735. 行星碰撞
     *
     * @param asteroids
     * @return
     */
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int asteroid : asteroids) {
            if (stack.isEmpty()) {
                stack.push(asteroid);
                continue;
            }
            while (!stack.isEmpty()) {
                int pre = stack.peek();
                //如果两个是一样的方向则保存
                if (pre > 0 && asteroid < 0) {
                    int absAsteroid = Math.abs(asteroid);
                    if (absAsteroid > pre) {

                    }
                } else if (pre < 0 && asteroid > 0) {

                } else {
                    stack.push(asteroid);
                    break;
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        char[] chars = new char[27];
        System.out.println(Arrays.toString(chars));
        System.out.println(chars[0]);
    }


}


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

@Data
class LocationInfo {
    private long locationId;
    private long buildingId;

    public static LocationInfo of(long locationId, long buildingId) {
        LocationInfo response = new LocationInfo();
        response.setLocationId(locationId);
        response.setBuildingId(buildingId);
        return response;
    }
}

@Data
class DistributeLocationInfo extends LocationInfo {
    /**
     * 档位
     * 0:优先项目, 1:[0, 1000], 2:[1000, 3000], 3:[3000, 5000], 4:[5000, ]
     */
    private int level;

    private Boolean alternate = Boolean.FALSE;

    public static DistributeLocationInfo of(LocationInfo info, int level) {
        return DistributeLocationInfo.of(info.getLocationId(), info.getBuildingId(), level);
    }

    public static DistributeLocationInfo of(long locationId, long buildingId, int level) {
        DistributeLocationInfo dis = new DistributeLocationInfo();
        dis.setLocationId(locationId);
        dis.setBuildingId(buildingId);
        dis.setLevel(level);
        return dis;
    }
}

class RandomizedSet {

    private Map<Integer, Integer> map;
    private int[] arr;
    private int index = -1;
    private Random random;

    public RandomizedSet() {
        map = new HashMap<>();
        arr = new int[20_0000];
        random = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        arr[index++] = val;
        map.put(val, index);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int removeIdx = map.remove(val);
        if (removeIdx != index) map.put(arr[index], removeIdx);
        arr[removeIdx] = arr[index--];
        return true;
    }

    public int getRandom() {
        return arr[random.nextInt(index + 1)];
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


class AllOne {

    private Map<String, Integer> map;
    private int maxCount;
    private int minCount;
    private String maxCountStr;
    private String minCountStr;

    public AllOne() {
        map = new HashMap<>();
        maxCount = 0;
        minCount = 0;
    }

    public void inc(String key) {
        int count = map.getOrDefault(key, 0) + 1;
        if (count == 1 || count <= minCount) {
            minCountStr = key;
            minCount = count;
        }
        if (count >= maxCount) {
            maxCountStr = key;
            maxCount = count;
        }
        map.put(key, count);

    }

    public void dec(String key) {
        int count = map.get(key);
        if (count == 1) {
            map.remove(key);
            return;
        }
        map.put(key, count - 1);
    }

    public String getMaxKey() {
        return maxCountStr;
    }

    public String getMinKey() {
        return minCountStr;
    }
}

class Solution {

    private int[] nums;
    private Map<Integer, List<Integer>> map;

    public Solution(int[] nums) {
        this.nums = nums;
        map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            final List<Integer> list = map.getOrDefault(nums[i], new ArrayList<>());
            list.add(i);
            map.put(nums[i], list);
        }
    }

    public int pick(int target) {
        final List<Integer> list = map.get(target);
        final int i = new Random().nextInt(list.size());
        return list.get(i);
    }
}

class PacificAtlanticClass {
    private int n, m;
    int[][] g;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        g = heights;
        m = g.length;
        n = g[0].length;
        Deque<int[]> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
        boolean[][] res1 = new boolean[m][n], res2 = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    res1[i][j] = true;
                    d1.addLast(new int[]{i, j});
                }
                if (i == m - 1 || j == n - 1) {
                    res2[i][j] = true;
                    d2.addLast(new int[]{i, j});
                }
            }
        }
        bfd(d1, res1);
        bfd(d2, res2);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (res1[i][j] && res2[i][j]) {
                    result.add(List.of(i, j));
                }
            }
        }
        return result;
    }

    int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    private void bfd(Deque<int[]> d, boolean[][] rest) {
        while (!d.isEmpty()) {
            final int[] ints = d.pollFirst();
            int x = ints[0], y = ints[1], t = g[x][y];

            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (rest[nx][ny] || t > g[nx][ny]) continue;
                d.addLast(new int[]{nx, ny});
                rest[nx][ny] = true;
            }
        }
    }

}

class RecentCounter {

    private int left;
    private int right;
    private int count;
    private boolean flag;

    public RecentCounter() {
        this.count = 0;
        this.left = 0;
        this.right = 0;
        this.flag = true;
    }

    public int ping(int t) {
        if (flag) {
            flag = false;
            left = t - 3000;
            right = t;
            count++;
        } else {
            int tempLeft = t - 3000;
            if (tempLeft >= left && tempLeft <= right) {
                count++;
            }
        }
        return count;
    }
}

/**
 * 6093. 设计一个文本编辑器
 */
class TextEditor {
    private StringBuilder sb;
    private int curIndex;

    public TextEditor() {
        this.sb = new StringBuilder("");
        this.curIndex = 0;
    }

    public void addText(String text) {
        sb.append(text);
        curIndex = sb.length() - 1;
    }

    public int deleteText(int k) {
        if (curIndex <= k) {
            final String substring1 = sb.substring(curIndex);
            sb = new StringBuilder();
            sb.append(substring1).append(substring1);
        } else {
            final String substring = sb.substring(0, curIndex - k);
            final String substring1 = sb.substring(curIndex);
            sb = new StringBuilder();
            sb.append(substring).append(substring1);
        }
        return Math.min(curIndex, k);
    }

    public String cursorLeft(int k) {
        if (curIndex <= k) {
            curIndex = 0;
            return "";
        }
        curIndex -= k;
        return sb.subSequence(0, curIndex).toString();
    }

    public String cursorRight(int k) {
        curIndex = Math.min(sb.length() - 1, curIndex + k);
        return sb.subSequence(Math.max(curIndex - k, 0), curIndex).toString();

    }

    public static void main(String[] args) {
        TextEditor instance = new TextEditor();
        instance.addText("leetcode");
        instance.deleteText(4);
        instance.addText("practice");
        instance.cursorRight(3);
        instance.cursorLeft(8);
        instance.deleteText(10);
        instance.cursorLeft(2);
        instance.cursorRight(6);

    }
}

class WaitNotifyDemo {

    static Object lock = new Object();

    public static void main(String[] args) {
        new Thread(() -> {
            synchronized (lock) {
                System.out.println(Thread.currentThread().getName() + " come in.");
                try {
                    lock.wait();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            System.out.println(Thread.currentThread().getName() + " 换醒.");
        }, "Thread A").start();

        new Thread(() -> {
            synchronized (lock) {
                lock.notify();
                System.out.println(Thread.currentThread().getName() + " 通知.");
            }
        }, "Thread B").start();
    }
}

class Codec {

    private Map<String, String> map = new HashMap<>();

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        final String domain = getDomain(longUrl);
        final String uri = getUri(longUrl);
        final String domainEncode = String.valueOf(domain.hashCode());
        final String uriEncode = String.valueOf(uri.hashCode());
        map.put(domainEncode, domain);
        map.put(uriEncode, uri);
        final String replace = longUrl.replace(domain, domainEncode);
        final String replace1 = replace.replace(uri, uriEncode);
        return replace1;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        final String domain = getDomain(shortUrl);
        final String uri = getUri(shortUrl);
        final String domainDecode = map.get(domain);
        final String uriDecode = map.get(uri);
        final String replace = shortUrl.replace(domain, domainDecode);
        final String replace1 = replace.replace(uri, uriDecode);
        return replace1;
    }

    private String getDomain(String url) {
        return url.substring(url.indexOf(':') + 3, url.indexOf('.'));
    }

    private String getUri(String url) {
        final String uri = url.substring(url.indexOf("."));
        return uri.substring(uri.indexOf("/") + 1);
    }
}

class MyCalendar {

    private List<int[]> list;

    public MyCalendar() {
        list = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        for (int[] ints : list) {
            if (end < ints[0] || start >= ints[1]) {
                continue;
            }
            return false;
        }
        list.add(new int[]{start, end});
        return true;
    }
}

class MagicDictionary {

    private List<String> list;

    public MagicDictionary() {
        list = new ArrayList<>();
    }

    public void buildDict(String[] dictionary) {
        list.addAll(Arrays.asList(dictionary));
    }

    public boolean search(String searchWord) {
        final char[] charArray = searchWord.toCharArray();
        for (String s : list) {
            if (s.length() != charArray.length) {
                continue;
            }
            int count = 0;
            for (int i = 0; i < charArray.length; i++) {
                if (charArray[i] != s.charAt(i)) {
                    count++;
                }
            }
            if (count == 1) {
                return true;
            }
        }
        return false;
    }
}